#define _CRT_SECURE_NO_WARNINGS 1
/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* copyRandomList(struct Node* head) {
	struct Node* cur = head;

	while (cur != NULL)
	{
		struct Node* next = cur->next;
		struct Node* NewNode = (struct Node*)malloc(sizeof(struct Node));
		NewNode->val = cur->val;
		cur->next = NewNode;
		NewNode->next = next;

		cur = next;

	}

	cur = head;

	while (cur != NULL)
	{
		struct Node* copy = cur->next;
		struct Node* next = copy->next;


		if (cur->random == NULL)
			copy->random = NULL;

		else
		{
			copy->random = cur->random->next;
		}
		cur = next;
	}

	struct Node* copyhead = NULL;
	struct Node* copytail = NULL;
	cur = head;

	while (cur != NULL)
	{

		struct Node* copy = cur->next;
		struct Node* next = copy->next;

		if (copytail == NULL)

			copyhead = copytail = copy;

		else
		{

			copytail->next = copy;
			copytail = copytail->next;
		}
		cur = next;
	}

	return copyhead;
}